On a conjecture of Gentner and Rautenbach

摘要

Gentner and Rautenbach conjectured that the size of a minimum zero forcingset in a connected graph on $n$ vertices with maximum degree $3$ is at most$\frac{1}{3}n+2$. We disprove this conjecture by constructing a collection ofconnected graphs $\{G_n\}$ with maximum degree 3 of arbitrarily large orderhaving zero forcing number at least $\frac{4}{9}|V(G_n)|$.